#include "doublelist.h"

DoubleList::~DoubleList(){
	NodePtr current = head;
	while(current != nullptr){
		NodePtr nextNode = current->next;
		delete current;
		current = nextNode;
	}
}
void DoubleList::insertAtHead(int value){
	NodePtr newNode = new DoubleListNode(value);
	
	if(isEmpty()){
		head = newNode;
		newNode->next = nullptr;
		newNode->prev = nullptr;
		return;
	}
	newNode->next = head; //将新节点的next保存head指向的节点
	newNode->prev = nullptr;
	head->prev = newNode; //将头节点的next保存新节点
	head = newNode; //将head指向新节点
}

void DoubleList::insertAtTail(int value){
	NodePtr newNode = new DoubleListNode(value);
	if(isEmpty()){
		head = newNode;
		newNode->next = nullptr;
		newNode->prev = nullptr;
		return;
	}
	NodePtr currnt = head;
	while(currnt->next != nullptr){
		currnt = currnt->next;
	}
	currnt->next = newNode;
	newNode->prev = currnt;
	newNode->next = nullptr;
}


void DoubleList::printDllForward(){
	if(isEmpty()){
		std::cout<<"Double linked list is empty!"<<std::endl;
		return;
	}	
	
	NodePtr current = head;
	std::cout<<"Double list: ";
	while(current != nullptr){
		std::cout<<current->val<<" ";
		current = current->next;
	}
	std::cout<<std::endl;
}

void DoubleList::printDllBackward(){
	if(isEmpty()){
		std::cout<<"Double linked list is empty!"<<std::endl;
		return;
	}	
	NodePtr current = head;
	while(current->next != nullptr){
		current = current->next;
	}
	
	std::cout<<"Double list: ";
	while(current){
		std::cout<<current->val<<" ";
		current = current->prev;
	}
	std::cout<<std::endl;
}
int DoubleList::getSzie() const{
	if(isEmpty()){
		return 0;
	}
	int count = 0;
	NodePtr current = head;
	while(current){
		++count;
		current = current->next;
	}
	return count;
}

void DoubleList::deleteAtHead(){
	if(isEmpty()){
		return;
	}
	NodePtr oldNode = head;
	head = head->next;
	if(head)
		head->prev = nullptr;
	delete oldNode;
}

void DoubleList::deleteAtTail(){
	if(isEmpty()){
		return;
	}
	NodePtr current = head;
	
	while(current->next != nullptr){
		current = current->next;
	}
	
	//链表可能仅有一个节点的情况
	if(current->prev != nullptr)
		current->prev->next = nullptr;
	else
		head = nullptr;
	delete current;
}

void DoubleList::deleteValue(int value){
	if(isEmpty()){
		return;
	}
	NodePtr current = head;
	while(current && current->val != value){
		current = current->next;
	}
	if(current == nullptr)
		return;
	if(current->prev != nullptr)
		current->prev->next = current->next;
	else
		head = current->next;
	if(current->next != nullptr)
		current->next->prev = current->prev;
	delete current;
}

void DoubleList::deleteAtPosition(int position){
	if(isEmpty()){
		return;
	}
	NodePtr current = head;
	for(int i = 0; i < position && current; ++i){
		current = current->next;
	}
	
	if(current == nullptr)
		return;
	if(current->prev != nullptr)
		current->prev->next = current->next;
	else
		head = current->next;
	if(current->next != nullptr)
		current->next->prev = current->prev;
	
	delete current;
}



NodePtr DoubleList::findFirst(int value){
	if(isEmpty())
		return nullptr;
	
	NodePtr current = head;
	while(current->val != value && current){
		current = current->next;
	}
	if(current)
		return current;
}

std::vector<NodePtr> DoubleList::findAll(int value){
	std::vector<NodePtr> temp_Node;
	if(isEmpty()){
		temp_Node.push_back(nullptr);
		return temp_Node;
	}
	
	NodePtr current = head;
	while(current){
		if(current->val == value && current)
			temp_Node.push_back(current);
		current = current->next;
	}
	return temp_Node;
}

NodePtr DoubleList::getNodeAt(int position){
	if(isEmpty())
		return nullptr;
	if(position < 0 && position > getSzie())
		return nullptr;
	NodePtr current = head;
	int dex = 0;
	while(current && dex != position){
		current = current->next;
		++dex;
	}
	return current;
}
NodePtr DoubleList::findMiddle(){
	if(isEmpty())
		return nullptr;
	if(!hasCircle())
		std::cerr << "错误：链表包含环，无法查找中间节点！" << std::endl;
	NodePtr fast = head;
	NodePtr slow = head;
	
	while(fast->next != nullptr && fast != nullptr){
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}
bool DoubleList::hasCircle(){
	if(isEmpty())
		return false;
	NodePtr fast = head;
	NodePtr slow = head;
	while(fast != nullptr && fast->next != nullptr){
		fast = fast->next->next;
		slow = slow->next;
		if(fast == slow)
			return true;
	}
	return false;
}

/*假设链表头到环入口的距离为 a，环的长度为 b，相遇点距离环入口的距离为 c。当快慢指针相遇时：
慢指针走过的总距离：S = a + m*b + c（m 为慢指针在环内绕的圈数）。
快指针走过的总距离：F = a + n*b + c（n 为快指针在环内绕的圈数，且 n > m）。
F = 2S ⇒ a + n*b + c = 2(a + m*b + c)
a + c = (n - 2m) * b ⇒ a = (n - 2m) * b - c
即 a = k*b - c（k 为整数，表示环的圈数）。
2. 相遇后寻找入口节点
根据上述推导，当快慢指针在环内相遇后：
将慢指针放回链表头。
快慢指针以相同速度（每次 1 步）移动。
当慢指针再次移动 a 步到达环入口时，快指针从相遇点出发，移动 k*b - c 步，恰好也到达环入口（因为 c + (k*b - c) = k*b，即绕环 k 圈后回到入口）。
*/
NodePtr DoubleList::findCycleEntry() {
	if (isEmpty()) return nullptr;
	
	// 步骤1：检测环，获取相遇点
	NodePtr slow = head;
	NodePtr fast = head;
	bool hasCycle = false;
	
	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next->next;
		
		if (slow == fast) {  // 相遇点
			hasCycle = true;
			break;
		}
	}
	
	if (!hasCycle) return nullptr;
	
	// 步骤2：将slow放回起点，快慢指针同速移动，再次相遇即入口
	slow = head;
	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;  // 此时fast从相遇点开始，每次移动1步
	}
	
	return slow;  // 返回环入口节点
}

NodePtr DoubleList::findFirstIf(std::function<bool(int)> condition){
	if(isEmpty())
		return nullptr;
	NodePtr current = head;
	while(current){
		if(condition(current->val))//condation是一个可调用对象，类似与函数调用
			return current;
		current = current->next;
	}
	return nullptr;
}

std::vector<NodePtr> DoubleList::findAllIf(std::function<bool(int)> condition)
{
	std::vector<NodePtr> temNode;
	if(isEmpty()){
		temNode.push_back(nullptr);
		return temNode;
	}
	
	NodePtr current = head;
	while(current){
		if(condition(current->val)){
			temNode.push_back(current);
		}
		current = current->next;
	}	
	
	if(temNode.empty()){
		temNode.push_back(nullptr);
		std::cout<<"查无节点";
		return temNode;
	}
}

int DoubleList::getPosition(NodePtr node){
	if(isEmpty())
		return -1;
	
	NodePtr current = head;
	int count = 0;
	while(current){
		if(current == node){
			return count;
		}
		current = current->next;
		++count;
	}
}

bool DoubleList::contains(NodePtr node){
	if(isEmpty())
		return false;
	
	NodePtr current = head;
	while(current){
		if(current == node)
			return true;
		current = current->next;
	}
	return false;
}

bool DoubleList::containsValue(int value){
	if(isEmpty())
		return false;
	
	NodePtr current = head;
	while(current){
		if(current->val == value)
			return true;
		current = current->next;
	}
	return false;
}

std::pair<NodePtr, int> DoubleList::findMax() {
	if (isEmpty()) return {nullptr, 0};  // 空链表返回{nullptr, 0}
	
	NodePtr current = head;
	NodePtr maxNode = head;
	int maxValue = current->val;
	
	while (current != nullptr) {
		if (current->val > maxValue) {
			maxValue = current->val;
			maxNode = current;
		}
		current = current->next;
	}
	
	return {maxNode, maxValue};  // 返回{节点指针, 最大值}
}

void DoubleList::insertBatchAtHead(const std::vector<int>& values) {
	if (values.empty()) return;
	
	NodePtr newHead = nullptr;
	NodePtr newTail = nullptr;
	
	for (int val : values) {
		NodePtr newNode = new DoubleListNode(val);
		if (!newHead) {
			newHead = newNode;
			newTail = newNode;  // 第一个节点是头也是尾
		} else {
			newNode->next = newHead;
			newNode->prev = nullptr;
			newHead->prev = newNode;
			newHead = newNode;  // 更新头节点
			// newTail 保持不变
		}
	}
	
	if (head) {
		newTail->next = head;  // 子链表尾接原链表头
		head->prev = newTail;  // 原链表头的前驱指向子链表尾
	}
	head = newHead;  // 更新全局头指针
}

void DoubleList::insertBatchAtTail(const std::vector<int>& values){
	if(values.empty())
		return;
	for (int val : values)
		insertAtTail(val);
}

void DoubleList::sort(){
	if(!head || !head->next)//链表为空或只有一个节点
		return;
	
	NodePtr sortedNode = nullptr; //指向临时链表头节点的头指针
	NodePtr current = head;
	
	while(current){
		NodePtr nextNode = current->next; //保存下一个即将处理的节点
		//// 情况1：插入到 sortedHead 前面（current 比 sortedHead 小或链表为空）
		if(!sortedNode || sortedNode->val >= current->val){
			current->next = sortedNode;
			if(sortedNode)
				sortedNode->prev = current;
			current->prev = nullptr;
			sortedNode = current;
		}
		else{ //在临时链表中进行查找排序
			NodePtr tempNode = sortedNode;
			while(tempNode->next && tempNode->next->val < current->val){
				tempNode = tempNode->next; //找到第一个比current节点大的前驱节点
			}
			//插入到tempNode之后
			current->next = tempNode->next;
			if(tempNode->next)//防止tempNode的下一个节点为空，对其进行操作产生未定义行为
				tempNode->next->prev = current;
			tempNode->next = current;
			current->prev = tempNode;
		}
		current = nextNode;
	}
	head = sortedNode;
}

